It is of critical importance to improve toughness, strength, and wear-resistance together for the development of advanced structural materials. Herein, we report on the synthesis of unoxidized graphene/alumina composite materials having enhanced toughness, strength, and wear-resistance by a low-cost and environmentally benign pressure-less-sintering process. The wear resistance of the composites was increased by one order of magnitude even under high normal load condition (25 N) as a result of a tribological effect of graphene along with enhanced fracture toughness (KIC) and flexural strength (σf) of the composites by ~75% (5.60 MPa·m1/2) and ~25% (430 MPa), respectively, compared with those of pure Al2O3. Furthermore, we found that only a small fraction of ultra-thin graphene (0.25–0.5 vol%, platelet thickness of 2–5 nm) was enough to reinforce the composite. In contrast to unoxidized graphene, graphene oxide (G-O) and reduced graphene oxide (rG-O) showed little or less enhancement of fracture toughness due to the degraded mechanical strength of rG-O and the structural defects of the G-O composites.